package com.da.javatest.algorithm;

import java.util.Arrays;

/**
 * @author chenlida
 * @date 2019/3/28 11:06
 * @description
 */
public class QuickSort2 {
    public static void main(String[] args) {
        int[] data = {8, 10, 2, 3, 6, 1, 5};
        new QuickSort2().sort(data);
        System.out.println(Arrays.toString(data));
    }

    public void sort(int[] data) {
        quickSortInternally(data, 0, data.length - 1);
    }

    private void quickSortInternally(int[] data, int start, int end) {
        if (data == null || start < 0 || end > data.length - 1) {
            throw new IllegalArgumentException("Invalid Parameters");
        }
        if (start == end) { return; }
        int index = partition(data, start, end);
        if (index > start) {
            quickSortInternally(data, start, index - 1);
        }
        if (index < end) {
            quickSortInternally(data, index + 1, end);
        }
    }

    private int partition(int[] data, int start, int end) {
        int index = start + (int)(Math.random() * (end - start + 1));
        swap(data, index, end);
        int small = start - 1;
        for (index = start; index < end; index++) {
            if (data[index] < data[end]) {
                small++;
                if (small != index) {
                    swap(data, index, small);
                }
            }
        }
        swap(data, small + 1, end);
        System.out.println(small + 1);
        return small + 1;
    }

    private void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}
